1. Field of the Invention
This invention relates to computer systems, and more particularly, to methods and apparatus for selecting a scale for a texture map used in applying texture to computer output images.
2. History of the Prior Art
In three dimensional graphics, surfaces are typically rendered by assembling a plurality of polygons in a desired shape. The polygons are conventionally triangles having vertices which are defined by three dimensional coordinates in world space, by color values, and by texture coordinates among other values. The three dimensional coordinates are translated into screen coordinates in which horizontal and vertical values (x, y) define screen position and a depth value z determines how near a vertex is to the screen and thus whether and how that vertex is viewed with respect to other points at the same screen coordinates. The color values define the brightness of each of red/green/blue (r, g, b) colors at each vertex and thus the color at each vertex. The texture coordinates (u, v) define the coordinates of each vertex on a texture map defined by values stored in memory.
A texture map describes a pattern to be applied to the surface of the triangle to vary the color in accordance with the pattern. A texture map is a matrix of values which describe colors at intersections of a pair of integral texture coordinates. The placement of the values in the matrix describes a pattern which when applied to the surface of the triangle varies the colors in accordance with the pattern. Since the texture coordinates of the vertices of a triangle define the position of the triangle on the texture map, the texture coordinates determine the texture applied to each portion of the triangle. In turn, the three dimensional world space coordinates of the vertices of a triangle positioned on the texture map define the plane in which the texture map lies with respect to the screen surface. Other characteristics defining each vertex such as transparency and additional textures may also be included to provide more sophisticated rendering.
In order to provide the pixel data to be stored in a frame buffer by which a triangle may be drawn on the screen, the screen vertices of the particular triangle are first determined from the world space three dimensional coordinates. Determining the vertices of a triangle in screen space fixes the position of all of the pixels defining that triangle in screen space. Once the pixels are determined defining the triangle in screen space, the depth values, the color values, and the texture coordinates are determined across the surface of the triangle in world space and projected onto screen space so that these values are known for each pixel. Since the triangle lies in a plane in world space, the depth, color values, and texture coordinates vary linearly in world space within the triangle from one to the other of the vertices. The depth values, color values, and texture coordinates in world space are projected into screen space by a process termed perspective projection. Then, the texture coordinates are utilized to determine texture values from a particular texture map; and these texture values are utilized to modify the color values of each pixel in the triangle.
The texture coordinates u and v of each pixel provide an index into a map of texture values typically stored in memory which together describe a particular texture pattern that is to be applied to the surface of the triangle. If a texture map describes a brick wall, for example, then each individual screen pixel in the triangle covers some portion of the texture map; and a texture value may be derived using the u and v coordinates of the pixel; and this texture value reflects the texture of the brick wall at the portion of the map where that pixel lies. This texture value is then used to modify the r, g, b color values determined by interpolation and perspective projection for that pixel.
Texture coordinates obtained by the interpolation and perspective projection processes are not typically integer values. On the other hand, indexing into a texture map is accomplished using integral coordinates. Consequently, non-integral coordinates must somehow be used to obtain texture values. A simple method of obtaining texture values uses the closest integral u and v values for each pixel to index into the texture map and then selects the value at that intersection.
This simple method does not provide a very accurate representation of texture values. This may be better understood by considering the relationship of texels and pixels. A pixel defines a position at which a single color is placed to display one position in a triangle. A texel represents a single value which may be used with other values to determine which single color a pixel displays. If a pixel covers a number of texels, then many different texels should be evaluated to determine a final color for the pixel. If a pixel covers approximately one texel, then that texel might be the only texel considered in determining the color for that pixel. Consequently, if only a single texture value is used to determine the texture value for a pixel, the determination will not be correct in all instances.
A more accurate method of representing the texture pattern representing a pixel is a process called bilinear interpolation which utilizes the integer portion of the u and v coordinates to select four sets of integral coordinates surrounding the center of each pixel at which to index into a texture map. For each of the texture values determined, the method uses the fractional portion of the coordinates to weight the texture value (texel). These weighted portions (typically the four texture values closest to the intersection) are combined and blended into a more accurate representation for modifying the pixel color values to reproduce the texture pattern. This provides a more accurate representation of texture where a number of texels are covered by a pixel.
However, those skilled in the art have recognized that where a pixel covers a very large number of texture values on a texture map, only a small portion of those values will be represented in the texture value selected to modify the color of that pixel using the bilateral interpolation method just described. Consequently, a more accurate method of texture mapping has been devised. The method provides texture maps having a plurality of different scales covering the same textures. A texture map may be selected having a scale such that the pixels of the individual triangles cover relatively consistent numbers of texels. The process of selecting a texture value for a pixel then includes an initial step for each particular triangle being rendered in which a texture map is selected having a scale adapted to accurately represent textures for the pixels of that triangle. The conventional process by which scaling is accomplished is referred to as "mipmapping." The mipmapping process is described in a paper entitled "Pyramidal Parametrics," presented at Siggraph proceedings, 1984.
In order to make the scale selection process more accurate, an additional process by which texture maps of the two closest scales to a desired scale are selected, and the texture values provided by those two different texture maps are interpolated linearly to provide values closer to the desired scale. This process is often referred to as "trilinear mipmapping."
The mipmapping process provides relatively accurate scaling for rendering pixels on the screen if the triangle lies in a plane parallel to the screen surface. However, since the process assumes that the projection of a pixel onto the texture map is square or rectangular in shape and aligned to the same axes as the texture map, the process does not provide a correct estimate of the number of texels covered by a pixel especially if the vertices of the triangle being mapped are at significantly different depths so that the triangle is foreshortened by perspective and the pixels on any scan line projected into texture space are warped and of different sizes and shapes. To obtain a correct texture scale, a method must be capable of accurately describing the actual size of the warped and distorted shapes of pixels which are projected into texture space when three dimensional shapes are rendered in any significant perspective in two dimensional space.
It is desirable to provide a method for determining the scale to be used for a texture map for more realistically mapping texture values to pixels representing three dimensional shapes than has been possible with prior art methods.